package 力扣_树算法.遍历;

import java.util.*;

/**102.二叉树的层序遍历
 * @author zx
 * @create 2022-04-09 12:18
 */
public class 二叉树的层序遍历_102 {
    /**
     * 时间复杂度：每个点进队出队各一次, 故渐进时间复杂度为O(n)。
     * 空间复杂度：队列中元素的个数不超过 n 个, 故渐进空间复杂度为 O(n)。
     * @return
     * 在每一层遍历开始前,先记录队列中的结点数量 n (也就是这一层的结点数量)
     * 然后一口气处理完这一层的 n 个结点
     *
     * 二叉树的层序遍历的变种题目挺多的，所以二叉树的层序遍历一定要理解着学习
     * 而其它三种遍历方式就不会这样了
     */
    public List<List<Integer>> levelOrder(TreeNode root) {
        //要返回的结果集合
        List<List<Integer>> res = new ArrayList<>();
        if(root == null){
            return res;
        }
        //借助队列实现遍历过程
        Deque<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        //在while循环的每一轮中,都是将当前层的所有结点出队列
        //再将下一层的所有结点入队列,这样就实现了层序遍历。
        while(!queue.isEmpty()){
            //保存当前层的元素
            List<Integer> level = new ArrayList<>();
            //取出当前层的所有元素添加进level
            int levelCount = queue.size();
            // 这里一定要使用固定大小size，不要使用queue.size(),因为que.size是不断变化的
            for(int i = 0;i < levelCount;i++){
                //队列中弹出节点node,加入到结果中
                TreeNode node = queue.poll();
                level.add(node.val);
                if(node.left != null){
                    queue.offer(node.left);
                }
                if(node.right != null){
                    queue.offer(node.right);
                }
            }
            res.add(level);
        }
        return res;
    }

    /**
     * 时间复杂度O(N)   空间复杂度O(N)
     * @return
     */
    public List<List<Integer>> levelOrder2(TreeNode root) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if(root == null){
            return res;
        }
        helper(root,0,res);
        return res;
    }

    private void helper(TreeNode root,int level,List<List<Integer>> res){
        if(root == null){
            return;
        }
        //level：代表当前层
        if(res.size() == level){
            res.add(new ArrayList<Integer>());
        }
        res.get(level).add(root.val);
        helper(root.left,level + 1,res);
        helper(root.right,level + 1,res);
    }
}
